//解数独
class Solution {
public:
    //思路就是利用回溯 每行每列的空位置一个一个试
    void solveSudoku(vector<vector<char>>& board) 
    {
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.') continue;
                for(char c='1';c<='9';c++)
                {
                    if(isValid(board,i,j,c))
                    {
                        board[i][j]=c;
                        bool flag=dfs(board);
                        if(flag) return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board,int row,int col,char val)
    {
        for(int i=0;i<board.size();i++)
        {
            if(board[row][i]==val) return false;
            if(board[i][col]==val) return false;
        }
        //九宫格内 开始位置只有0 3 6
        int startx=(row/3)*3;
        int starty=(col/3)*3;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(board[startx+i][starty+j]==val) return false;
            }
        }
        return true;
    }
};